人工智能中的约束求解和优化专题｜《中国科学：信息科学》英文版

专题简介

约束求解和优化算法是人工智能领域中一个重要的研究方向, 并在过去的几十年间取得了广泛的应用, 成功地解决了工业领域的诸多问题. 随着互联网行业和人工智能技术的发展, 相关的应用领域产生了一系列新的大规模优化问题, 同时为约束求解和优化算法方向带来了新的挑战.

SCIENCE CHINA Information Sciences在2021年第64卷第5期组织出版了“人工智能中的约束求解和优化” (Special Focus on Constraints and Optimization in Articial Intelligence), 旨在报道约束求解和优化算法的前沿进展. 经过高效严格的同行评审, 本专题共收录5篇论文, 涵盖了局部搜索算法、近似算法、大规模图优化、神经网络优化和演化算法分析等.

“Focal distance tabu search”(Glover 等) 介绍了禁忌搜索算法的一个变种, 名为焦距禁忌搜索. 焦距禁忌搜索在传统禁忌搜索的基础上, 加入了周期性的扩散搜索, 强制使得算法尽量远离当前最好解, 直到算法访问的解的目标函数值离当前最好解达到一定阈值. 该方法可以用来改进其他的启发式搜索算法.

“Learning dynamics of gradient descent optimization in deep neural networks”(Wu等) 针对深度学习模型中梯度优化器的学习问题, 从随机动力学微分方程上进行了解释, 并构建了一阶、二阶传递函数控制模型, 对随机梯度下降(stochastic gradient descent, SGD)方法及其动量改善策略的作用机理、学习过程进行了研究.

“On the robustness of median sampling in noisy evolutionary optimization”(Bian 等)为降低演化算法求解带噪问题时噪声的负面影响, 在现有均值采样策略的基础上提出了一种中位数采样策略, 并从理论上证明了该策略的有效性以及适用条件.

“An approximation algorithm fork-median with priorities”(Zhang 等)提出了构建设施星型结构的确定化舍入方法, 设计了优先k-中值问题近似率为(6.6743+ ) 的近似算法. 这是目前所知关于优先k-中值问题的第一个常数近似算法.

“Solving diversied top-kweight clique search problem”(Zhou 等)给出了一种多样性top-k加权团问题的求解方法, 该方法将多样性top-k加权团问题编码为最大加权可满足问题, 进而采用目标问题的求解器求解原始问题.